package org.algorithm.biubiu.wheel_1.回溯算法;

import org.junit.Test;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 给定一个整数数组  nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/partition-to-k-equal-sum-subsets/
 */
public class $5月1日$划分为k个相等的子集 {



    @Test
    public void test1(){
        int[] num = {1,1,1,1,2,2,2,2};
        boolean b = canPartitionKSubsets(num, 2);
    }
    HashMap<Integer,List<List<Integer>>> res = new HashMap();
    int k;
    int[] nums;
    public boolean canPartitionKSubsets(int[] nums, int k) {
        this.nums = nums;
        this.k = k;

        backtrack(0,0);
        for (Map.Entry<Integer, List<List<Integer>>> integerListEntry : res.entrySet()) {
            if(integerListEntry.getValue().size()==k){
                return true;
            }

        }
        return false;
    }

    List<Integer> cur = new ArrayList();

    public void backtrack(int step,int sum){
        List<List<Integer>> curEle = res.getOrDefault(sum,new ArrayList());
        curEle.add(new ArrayList(cur));
        res.put(sum,curEle);
        // 放入map
        for(int i =0;i<nums.length;i++){
            cur.add(nums[i]);
            sum+=nums[i];
            backtrack(i+1,sum);


            sum-=nums[i];
            cur.remove(cur.size()-1);
        }
    }

}
